package search;

public class BinarySearch {
    private int[] data;

    public BinarySearch(int[] data){
        this.data = data;
    }

    /**
     * 递归算法
     * @param target
     * @return
     */
    public int search(int target){
        int min = 0;
        int max = data.length - 1;
        int n = 0;
        while(true){
            n = (min + max)/2;
            if(target > data[n])
                min = n + 1;
            if(target < data[n])
                max = n - 1;
            if(target == data[n])
                return n;
            if(max < min)
                return -1;
        }
    }

    /**
     * 非递归算法
     * @param target
     * @param min
     * @param max
     * @return
     */
    public int search2(int target,int min,int max){
        if(min > max)
            return -1;
        int n = (min + max)/2;
        if(target > data[n])
            min = n + 1;
        if(target < data[n])
            max = n -1;
        if(target == data[n])
            return n;
        else
            return search2(target,min,max);
    }
    public static int binarySearch(int[] nums, int key) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (nums[m] == key) {
                return m;
            } else if (nums[m] > key) {
                h = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
    /*二分查找的变种形式
    * 当循环体退出时，不表示没有查找到 key，因此最后返回的结果不应该为 -1。
    * 为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等。*/
    public int binarySearch2(int[] nums, int key) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] >= key) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return l;//为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等
    }

    public static void main(String[] args) {
        int[] ints = {1,2,7,9,33,55,66,100};
        //BinarySearch bs = new BinarySearch(ints);
        /*System.out.println("非递归算法：");
        System.out.println("在数组的第"+bs.search(26)+"个位置");
        System.out.println("在数组的第"+bs.search(66)+"个位置");
        System.out.println("递归算法：");
        System.out.println("在数组的第"+bs.search2(50,0,ints.length-1)+"个位置");
        System.out.println("在数组的第"+bs.search2(55,0,ints.length-1)+"个位置");*/
        int []nums=new int[]{1,2,3,4,5,6};
        int i = binarySearch(nums, 4);
        System.out.println(i);

    }

}
